edge depth first search
https://gyazo.com/1957f5e7122ed77931ef8d0dbf313033
Given an undirected graph, we want to orient the edges so that they become strongly connected components.
1 is a vertex depth-first search, which means there are edges that cannot be passed.
3 is the correct edge depth-first search
2 is an inadvertent mistake.
I painted it at the right time to stack the edges to be visited in the future.
The edge coming out of the vertex of C is missing.
3
code:python
for v1, v2 in edgelist:
if (v1, v2) not in answer:
def visit(e):
(v1, v2) = e
if v3 == v1:
continue
if (v2, v3) in answer:
continue
visit((v2, v3))
visit((v1, v2))
2
code:python
for v1, v2 in edgelist:
if (v1, v2) not in answer:
while stack:
v1, v2 = stack.pop()
if v3 == v1:
continue
if (v2, v3) in answer:
continue
stack.append((v2, v3))
2 implemented without recursive calls
Make the timing of the application the timing of actually following the edge.
Check that the already painted edge is not painted before applying it, since it may already be in the stack.
code:python
for v1, v2 in edgelist:
if (v1, v2) not in answer:
while stack:
v1, v2 = stack.pop()
if (v1, v2) in answer:
continue
if v3 == v1:
continue
stack.append((v2, v3))
---
This page is auto-translated from /nishio/辺の深さ優先探索. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.